{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 摘要\n",
    "\n",
    "1.最大熵模型\n",
    "\n",
    "2.改进的迭代尺度法\n",
    "\n",
    "3.牛顿法、拟牛顿法\n",
    "\n",
    "\n",
    "\n",
    "### 1.最大熵模型\n",
    "\n",
    "最大熵模型是我们在建立模型时的一个准则：在所有可能的概率模型中，熵最大的模型是最好的模型。\n",
    "\n",
    "上面这句话该怎么理解呢？给大家举个例子：我们有一个骰子，那每一面朝上的概率为多少？大多数人都会回答1/6。为什么这样猜测呢？因为对一个“一无所知”骰子，假定它每一面朝上概率均等是最安全的，我们没有对未知的情况做任何主观假设，这时其概率分布的信息熵最大。我们把这种模型称为“最大熵模型”。\n",
    "\n",
    "如果我们继续说，这个骰子被特殊处理过，“4”点朝上的概率为1/3，这种情况下每个面朝上的概率是多少？很多人认为其他面均为2/15，这种推断也是有道理的。当我们已知部分前提时，对未知分布最合理的推断就是在符合已知条件下最不确定或最随机的推断，这是我们可以做出的唯一不偏不倚的选择，因为任何其他的选择都意味着我们增加了其他的约束和假设，这些假设和约束根据我们所掌握的信息无法做出。\n",
    "\n",
    "假设离散随机变量X的概率分布为$P(X)$，则其熵为：\n",
    "$$\n",
    "H(P)=-\\sum_{x}^{}{P(x)logP(x)}\n",
    "$$\n",
    "这是熵的定义式。\n",
    "\n",
    "假设我们有训练集合$ T=\\left\\{ (x_1,y_1),(x_2,y_2),...(x_N,y_N) \\right\\} $，则我们可以根据训练样本得到经验分布\n",
    "$$\n",
    "\\tilde{P}(x,y)=\\tilde{P}(X=x,Y=y)=\\frac{cont(x,y)}{N}\n",
    "$$\n",
    "$$\n",
    "\\tilde{P}(x)=\\tilde{P}(X=x)=\\frac{count(x)}{N}\n",
    "$$\n",
    "下面需要定义特征函数 $f(x,y)$ :\n",
    "$$ f(x,y)=\\left\\{\n",
    "\\begin{array}{rcl}\n",
    "1,     &      & {x,y满足某一事实}\\\\\n",
    "0,     &      & {否则}\n",
    "\\end{array} \\right. \n",
    "$$\n",
    "\n",
    "当 $f(x,y)$ 满足这个事实时取1，否则取值为0.\n",
    "\n",
    "设特征函数  $ f $ 在训练集中关于经验分布$ \\tilde{P}(x,y) $的数学期望为：\n",
    "$$\n",
    "E_\\tilde{p}(f)=\\sum_{x,y}^{}{\\tilde{P}(x,y)f(x,y)}\n",
    "$$\n",
    "特征函数 $f $ 在模型中关于 $P(x,y)$ 的数学期望为：\n",
    "$$\n",
    "E_p(f)=\\sum_{x,y}^{}{P(x,y)f(x,y)}\n",
    "$$\n",
    "根据贝叶斯公式，得\n",
    "$$\n",
    "E_p(f)=\\sum_{x,y}^{}{P(x)P(y|x)f(x,y)}\n",
    "$$\n",
    "上面的$ P(x) $我们近似用经验分布 $\\tilde{P}(x)$ 表示，得\n",
    "$$\n",
    "E_p(f)=\\sum_{x,y}^{}{P(x)P(y|x)f(x,y)}=\\sum_{x,y}^{}{\\tilde{P}(x)P(y|x)f(x,y)}\n",
    "$$\n",
    "在分类问题中，我们希望求得的就是条件概率$ P(y|x)$ 。\n",
    "\n",
    "在最大熵模型的定义中，我们说应首先保证模型满足已知的所有约束。这些约束应该这样提：从训练集中抽取若干(对分类问题有用的)特征，也就是我们之前定义的特征函数 f_i(x,y) ，然后找出特征函数的约束条件。为了让模型拟合训练数据，我们需要让： $E_p(f)=E_\\tilde{p}(f)$ ，即：\n",
    "$$\n",
    "\\sum_{x,y}^{}{\\tilde{P}(x,y)f(x,y)}=\\sum_{x,y}^{}{\\tilde{P}(x)P(y|x)f(x,y)}\n",
    "$$\n",
    "这样一个特征函数 $f_i(x,y) $就对应一个约束。\n",
    "\n",
    "在约束得到之后，因为我们模型是对 P(y|x) 建模，在满足约束的前提下使得模型的熵最大，首先得条件熵为：\n",
    "$$\n",
    "H(P(y|x))=-\\sum_{x,y}^{}{P(x)P(y|x)logP(y|x)}=-\\sum_{x,y}^{}{\\tilde{P}(x)P(y|x)logP(y|x)}\n",
    "$$\n",
    "条件熵的推导见我的另一篇文章：\n",
    "\n",
    "[决策树算法](https://zhuanlan.zhihu.com/p/29980400)\n",
    "\n",
    "另外对任意输入样例 $x $，它肯定属于某一个输出类别，所以：\n",
    "$$\n",
    "\\sum_{y}^{}{P(y|x)}=1\n",
    "$$\n",
    "因此最大熵模型就等价为如下最优化问题：\n",
    "$$\n",
    "\\left \\{ \n",
    "\\begin{array}{left}\n",
    "max &  & H(P(y|x))=-\\sum_{x,y}\\tilde P(x)P(y|x)log P(y|x) \\\\ \n",
    "s.t && E_\t\\Upsilon (f_i (x,y))=E_\t\\Upsilon (f_i (x,y)),i=1,2\\dots,n \\\\ \n",
    "&    &\\sum_y P(y|x)=1\n",
    "\\end{array}\n",
    "\\right. \n",
    "$$\n",
    "\n",
    "我们将最大化问题转化为最小化问题：\n",
    "$$\n",
    "\\left \\{ \n",
    "\\begin{array}{left}\n",
    "max &  & -H(P(y|x))=-\\sum_{x,y}\\tilde P(x)P(y|x)log P(y|x) \\\\ \n",
    "s.t && E_\t\\Upsilon (f_i (x,y))=E_\t\\Upsilon (f_i (x,y)),i=1,2\\dots,n \\\\ \n",
    "&    &\\sum_y P(y|x)=1\n",
    "\\end{array}\n",
    "\\right. \n",
    "$$\n",
    "\n",
    "解决这种带约束的优化问题，我们主要用拉格朗日乘子法，之前我们一起学习过，链接：\n",
    "\n",
    "[拉格朗日乘子法](https://zhuanlan.zhihu.com/p/30438416)\n",
    "\n",
    "引入拉格朗日乘子，定义拉格朗日函数 $L(P,\\lambda) $:\n",
    "$$\n",
    "L(P,\\lambda)=\\sum_{x,y}^{}{\\tilde{P}(x)P(y|x)logP(y|x)+\\lambda_0(1-\\sum_{y}^{}{P(y|x)})}+\\sum_{i=1}^{n}{\\lambda_i(E_p(f_i)-E_\\tilde{p}(f_i))}\n",
    "$$\n",
    "最优化的原始问题为：\n",
    "$$\n",
    "min_P max_\\lambda L(P,\\lambda)\n",
    "$$\n",
    "其对偶问题为：\n",
    "$$\n",
    "max_\\lambda min_P L(P,\\lambda)\n",
    "$$\n",
    "\n",
    "\n",
    "我们首先考虑对 $L(P,\\lambda)$ 对 $P(y|x)$ 的最小化，求导：\n",
    "$$\n",
    "\\frac{\\alpha L(P,\\lambda)}{\\alpha P(y|x)}=\\frac{\\alpha}{\\alpha P(y|x)}\\sum_{x,y}^{}{\\tilde{P}(x)P(y|x)logP(y|x)+\\lambda_0(1-\\sum_{y}^{}{P(y|x)})}+\\sum_{i=1}^{n}{\\lambda_i(E_p(f_i)-E_\\tilde{p}(f_i))}\n",
    "$$\n",
    "$$\n",
    "=\\sum_{x,y}^{}{\\tilde{P}(x)}(logP(y|x)+1-\\lambda_0-\\sum_{i=1}^{n}{\\lambda_if_i(x,y)})\n",
    "$$\n",
    "令上面导数等于0，在 $\\tilde{P}(x)>0$ 时，得\n",
    "$$\n",
    "logP(y|x)+1-\\lambda_0-\\sum_{i=1}^{n}{\\lambda_if_i(x,y)}=0\n",
    "$$\n",
    "$$\n",
    "logP(y|x)=-1+\\lambda_0+\\sum_{i=1}^{n}{\\lambda_if_i(x,y)}\n",
    "$$\n",
    "$$\n",
    "P(y|x)=e^{\\lambda_0-1}e^{\\sum_{i=1}^{n}{\\lambda_if_i(x,y)}}\n",
    "$$\n",
    "由约束条件 $\\sum_{y}^{}{P(y|x)}=1$ ，得\n",
    "$$\n",
    "\\sum_{y}^{}{P(y|x)}=\\sum_{y}^{}{e^{\\lambda_0-1}e^{\\sum_{i=1}^{n}{\\lambda_if_i(x,y)}}}=1\n",
    "$$\n",
    "$$\n",
    "e^{\\lambda_0-1}=\\frac{1}{\\sum_{y}^{}{e^{\\sum_{i=1}^{n}{\\lambda_if_i(x,y)}}}}\n",
    "$$\n",
    "令 $Z_\\lambda(x)=\\sum_{y}^{}{e^{\\sum_{i=1}^{n}{\\lambda_if_i(x,y)}}} $,称为规范化因子，得到对偶问题的极小解为：\n",
    "$$\n",
    "P_\\lambda (y|x)=e^{\\lambda_0-1}e^{\\sum_{i=1}^{n}{\\lambda_if_i(x,y)}}=\\frac{1}{Z_\\lambda (x)}e^{\\sum_{i=1}^{n}{\\lambda_if_i(x,y)}}\n",
    "$$\n",
    "我们令\n",
    "$$\n",
    "\\psi (\\lambda)=minL(P,\\lambda)=L(P_\\lambda,\\lambda)\n",
    "$$\n",
    "$$\n",
    "\\psi (\\lambda)=\\sum_{x,y}^{}{\\tilde{P}(x)P_\\lambda (y|x)logP_\\lambda (y|x)}+\\sum_{i=1}^{n}{\\lambda_i(\\sum_{x,y}^{}{\\tilde{P}(x,y)f_i(x,y)}-\\sum_{x,y}^{}{\\tilde{P}(x)P_\\lambda(y|x)f_i(x,y)})}\n",
    "$$\n",
    "上式不考虑 $\\lambda_0 $,经过化简得到：\n",
    "$$\n",
    "\\psi (\\lambda)=\\sum_{x,y}^{}{\\tilde{P}(x,y)\\sum_{i=1}^{n}{\\lambda_i}f_i(x,y)}-\\sum_{x}^{}{\\tilde{P}(x)logZ_\\lambda(x)}\n",
    "$$\n",
    "根据对偶问题所以我们需要最大化：\n",
    "$$\n",
    "max_\\lambda \\psi (\\lambda)=\\sum_{x,y}^{}{\\tilde{P}(x,y)\\sum_{i=1}^{n}{\\lambda_i}f_i(x,y)}-\\sum_{x}^{}{\\tilde{P}(x)logZ_\\lambda(x)}\n",
    "$$\n",
    "对偶函数的极大化其实等价于最大熵模型的极大似然估计，即求：\n",
    "$$\n",
    "L(\\lambda)=\\sum_{x,y}^{}{\\tilde{P}(x,y)\\sum_{i=1}^{n}{\\lambda_i}f_i(x,y)}-\\sum_{x}^{}{\\tilde{P}(x)logZ_\\lambda(x)} 的极大值 w^* 。\n",
    "$$\n",
    "上面的公式没有一个显式的解，我们需要借助数值的方法，一般可以采用改进的迭代尺度法、牛顿法和拟牛顿法、梯度下降法。下面我们主要介绍迭代尺度法和拟牛顿法。\n",
    "\n",
    "\n",
    "\n",
    "## 改进的迭代尺度法\n",
    "\n",
    "改进的迭代尺度法（improved iterative scaling，IIS）是一种最大熵模型学习的最优化算法。\n",
    "\n",
    "IIS的思想很简单：假设最大熵模型当前的参数向量为\n",
    "$$\n",
    "\\lambda=(\\lambda_1,\\lambda_2,...\\lambda_n)\n",
    "$$\n",
    "我们希望找到一个新的参数向量\n",
    "$$\n",
    "\\lambda+\\varrho =(\\lambda_1+\\varrho_1,\\lambda_2+\\varrho_2,...\\lambda_n+\\varrho_n)\n",
    "$$\n",
    "使得模型的对数似然函数值增大。如果能有这样一种参数向量更新的方法 $\\tau：w\\rightarrow w+\\varrho$ ，那就重复使用这一方法，直到找到对数似然函数的最大值。\n",
    "\n",
    "\n",
    "\n",
    "## 牛顿法和拟牛顿法\n",
    "\n",
    "### 1.牛顿法\n",
    "\n",
    "考虑无约束最优化问题：\n",
    "$$\n",
    "min f(x)\n",
    "$$\n",
    "牛顿法的主要思想：在现有的极小值估计值的附近对f(x)做二阶泰勒展开，进而找到极小点的下一个估计值，反复迭代直到算法收敛，其迭代公式为：\n",
    "$$\n",
    "x_{k+1}=x_k-\\frac{f'(x_k)}{f''(x_k)}\n",
    "$$\n",
    "当 x 为多维向量时， $x=(x_1,x_2,...,x_n)$\n",
    "$$\n",
    "f''(x)=H(x)=\\left[ \\frac{\\alpha^2f}{\\alpha x_i\\alpha x_j}\\right]_{n\\times n}\n",
    "$$\n",
    "称 $$H(x)$$ 为海塞矩阵(Hesse matrix)。\n",
    "$$\n",
    "g(x)=f'(x)\n",
    "$$\n",
    "所以迭代公式变为：\n",
    "$$\n",
    "x^{(k+1)}=x^{(k)}-H_k^{-1}g_k\n",
    "$$\n",
    "这就是牛顿法\n",
    "\n",
    "\n",
    "\n",
    "### 2.拟牛顿法\n",
    "\n",
    "在牛顿法中，我们需要计算海赛矩阵的逆矩阵 $H^{-1} $，这一计算比较复杂，当我们考虑用一个n阶矩阵 $G_{n\\times n}$ 来近似代替$ H^{-1}$ ，这个方法就叫做拟牛顿法。\n",
    "\n",
    "拟牛顿算法主要有$DFP$算法，$BFGS$算法和$Broyden$类算法。\n",
    "\n",
    "\n",
    "\n",
    "以上就是最大熵模型全部的内容，希望能给大家一些下一次我们一起学习$EM$算法。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
